A search engine is an algorithm, typically implemented on a general purpose computer, that traverses a space of possible candidate designs in a manner to try to find one or more improved candidate designs by trying to improve upon one or more objective functions. Search engines can be used to solve complex problems that are intractable and defy direct solution, or for which theoretically known approaches are impractical because they require too much time or other resources or are too inconvenient to bother modeling.
Search engines differ by the search space or design space on which they operate. For example, the design space of a typical parameter search engine is a subset of a multidimensional space of real numbers, i.e. Rn. Other candidate spaces are also possible, for example, data structures such as a tree, a graph, etc.
Search engines are used in a variety of disciplines ranging from academic research to industrial applications. Because of the widespread use of search engines, they have been carefully studied. Techniques have been discovered to improve performance and eliminate unproductive search paths. While some of the techniques and principles are generally applicable, other techniques or refinements are based on the specific nature of the problem in question.
One example of the need to refine search engine techniques is in engineering or industrial design problems in which there is a need to deal with uncertainty. For example, in the large-scale production of any manufacture, real-world considerations such as machine tolerances, individual variation in components and other factors affect the quality and performance of the final product. Such variations can often be regarded as random and modelled, for example, using a Gaussian probability distribution. Robustness is a characteristic of a design that qualifies how well that design performs in the face of variation. A robust design process refers to an approach to reducing the effects of variation by predicting the likely magnitude of such variations and accounting for them in the specifications, models and design of the product.
Since automated search techniques can be used to aid design, it is useful to consider incorporating robustness into automated search in a robust design process. One well-known approach to robust search problems is the “brute-force” Monte Carlo search method. Monte Carlo sampling is the process of drawing random samples from a process that has variation. The “brute-force” Monte Carlo search method replaces a standard objective function with a variation-induced objective function by taking a fixed number of Monte Carlo samples, then performing a statistical estimate on those samples, and trying to optimize those statistical estimates in the same manner as if they were deterministic objective functions. This method is combined with standard search engines that have typically originally been used in search on deterministic objective functions, e.g. evolutionary algorithms and simulated annealing. The “brute force” Monte Carlo search method is quite problem independent because it is independent of specific characteristics of the underlying variation; it just needs to be able to draw Monte Carlo samples. This makes it a very useful in attacking problems that are not solvable in closed form; it is, in general a very flexible approach to robust optimization, and is sometimes the only conceivable method of robust optimization for particular problems.
As is well known in statistical theory, increasing the sample size can reduce the amount of uncertainty in estimation of the underlying process. Accordingly, the standard technique to reduce the uncertainty in “brute-force” Monte Carlo search method is to increase the (pre-set) number of samples. Unfortunately, increasing the sample size increases the amount of computing power and other resources required. It is not uncommon to run 50 or even 500 Monte Carlo samples at a design point in order to keep uncertainty low. That means that “brute-force” Monte Carlo search need roughly 50 to 500 more computational effort than a comparable non-robust search. If the computing demands are excessive, then the finite amount of available resources, including time, may constrain the types of problems that can be solved by this approach. It is, therefore, desirable to provide a method that preserves the utility and power of such search engines while reducing the computing demands and constraints that are associated with existing methods.
Other types of search engines invented for robust design problems employ relatively fast, specialized algorithms that rely on a particular closed form description of the underlying process, or make assumptions about the underlying process. The advantage is that these techniques are able to use less computational effort than a generalized “brute force” Monte Carlo search method. The drawback is that these approaches are only able to solve a subset of all robust optimization problems.
In summary, the “brute force” Monte Carlo approach to robust design has the advantage of broad applicability and flexibility, with the disadvantage of needing significant computing resources. The approach of having specialized algorithms for robust design has the advantage of needing less computational resources, with the disadvantage of limited applicability and flexibility. There is a desire to have an approach to robust design that has broad applicability and flexibility, yet requires less computing resources than the “brute-force” Monte Carlo approach.